import java.util.ArrayList;
import java.util.List;

/**
 * 剑指 Offer 49. 丑数
 * https://leetcode-cn.com/problems/chou-shu-lcof/
 */
public class Solutions_Offer_49 {
    public static void main(String[] args) {
        int n1 = 5;  // output: 5
        int n2 = 6;  // output: 6
        int n3 = 7;  // output: 8
        int n4 = 8;  // output: 9
        int n5 = 9;  // output: 10
        int n6 = 10;  // output: 12

        List<Integer> inputs = new ArrayList<>();
        inputs.add(n1);
        inputs.add(n2);
        inputs.add(n3);
        inputs.add(n4);
        inputs.add(n5);
        inputs.add(n6);

        for (Integer input : inputs) {
            int result = nthUglyNumber(input);
            System.out.println(result);
        }
    }

    /**
     * 任意一个丑数都是由小于它的某一个丑数乘 2，乘 3 或者乘 5 得到的
     */
    public static int nthUglyNumber(int n) {
        int[] arr = new int[n];
        arr[0] = 1;
        int idx1 = 0, idx2 = 0, idx3 = 0;
        for (int i = 1; i < n; i++) {
            int n1 = arr[idx1] * 2;
            int n2 = arr[idx2] * 3;
            int n3 = arr[idx3] * 5;
            // 较小的丑数
            int minNum = Math.min(Math.min(n1, n2), n3);
            // 不能用 if...else if，需要用三次 if
            if (minNum == n1) {
                idx1 ++;
            }
            if (minNum == n2) {
                idx2 ++;
            }
            if (minNum == n3) {
                idx3 ++;
            }
            arr[i] = minNum;
        }
        return arr[n - 1];
    }
}
